class Solution {
public:
    // f1函数的含义：从(0,0)到(i,j)的最短路径
    // ij确定，这两个参数，确定下来，返回值就一定确定
    // 准备一个缓存表dp[i][j],可以通过
    int f2(vector<vector<int>>& grid, int i, int j,vector<vector<int>>&dp) {
        // 上来先判断一下是否命中缓存表
        // 如果不是-1，则按下面的展开
        // 如果是-1，说明这个过程之前遇到过

        if (dp[i][j] != -1) {
            return dp[i][j];
        }
        int ans = 0;
        // base case
        if (i == 0 && j == 0)
            ans = grid[0][0];
        else {
            int up = INT_MAX;
            int left = INT_MAX;
            if (i - 1 >= 0) // 如果有上面的
                up = f2(grid, i - 1, j,dp);
            if (j - 1 >= 0)//如果有左边
                left = f2(grid, i, j - 1,dp);
            ans= grid[i][j] + min(up, left);
        }
        //记录缓存，挂缓存
        dp[i][j]=ans;
        return ans;
    }
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();    // 行
        int n = grid[0].size(); // 列
        // 没算过表示-1
        vector<vector<int>> dp(
            m, vector<int>(n, -1)); // 初始化为m行，n列，值都为-1

        return f2(grid, grid.size() - 1, grid[0].size() - 1, dp);
    }
};


class Solution {
public:
    //f1函数的含义：从(0,0)到(i,j)的最短路径

    int f1(vector<vector<int>>&grid,int i,int j)
    {
        //base case
        if(i==0&&j==0)
            return grid[0][0];
        int up=INT_MAX;
        int left=INT_MAX;
        if(i-1>=0)//如果有上面的
            up=f1(grid,i-1,j);
        if(j-1>=0)
            left=f1(grid,i,j-1);
        return grid[i][j]+min(up,left);
    }
    int minPathSum(vector<vector<int>>& grid) {
        return f1(grid,grid.size()-1,grid[0].size()-1);
    }
};

